package 链表;

import java.util.PriorityQueue;

public class Solution {
    class ListNode{
        private int val;
        private ListNode next;
        private ListNode head;
        public ListNode(int val){
            this.val=val;
        }
    }
    //链表相加
    //题目连接:https://leetcode.cn/problems/add-two-numbers/
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode cur1=l1;
        ListNode cur2=l2;
        int t=0;
        ListNode newHead=new ListNode(0);
        ListNode prev=newHead;
        while(cur1!=null||cur2!=null||t!=0){
            if(cur1!=null){
                t+= cur1.val;
                cur1=cur1.next;
            }
            if(cur2!=null){
                t+=cur2.val;
                cur2=cur2.next;
            }
            prev.next=new ListNode(t%10);
            prev=prev.next;
            t/=10;
        }
        return newHead.next;
    }

    //题目连接:https://leetcode.cn/problems/swap-nodes-in-pairs/
    public ListNode swapPairs(ListNode head) {
        if(head==null||head.next==null){
            return head;
        }
        //定义一个虚拟头节点
        ListNode newHead=new ListNode(0);
        ListNode prev=newHead;
        newHead.next=head;
        ListNode cur=prev.next;
        ListNode next=cur.next;
        ListNode nnext=next.next;
        while(cur!=null&&next!=null){
            //交换节点
            prev.next=next;
            next.next=cur;
            cur.next=nnext;

            //修改指针
            prev=cur;
            cur=nnext;
            if(cur!=null){
                next=cur.next;
            }
            if(next!=null){
                nnext=next.next;
            }
        }
        return newHead.next;

    }


    //题目链接:https://leetcode.cn/problems/reorder-list/description/
    public void reorderList(ListNode head) {
        if(head==null||head.next==null||head.next.next==null){
            return;
        }
        //找到链表的中间位置
        ListNode slow=head;
        ListNode fast=head;
        while(fast!=null&&fast.next!=null){
            slow=slow.next;
            fast=fast.next.next;
        }
        //反转中间位置后面的链表
        ListNode head2=new ListNode(0);
        ListNode cur=slow.next;
        slow.next=null;
        //头插进行逆序链表
        while(cur!=null){
            ListNode next=cur.next;
            cur.next=head2.next;
            head2.next=cur;
            cur=next;
        }
        //下面就是合并两个链表
        ListNode cur1=head;
        ListNode cur2=head2.next;
        ListNode ret =new ListNode(0);
        ListNode prev=ret;
        while(cur1!=null){
            //先放第一个链表
            prev.next=cur1;
            prev=cur1;
            cur1=cur1.next;
            //放第二个链表
            if(cur2!=null){
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        // return ret.next;
    }

    //题目链接:https://leetcode.cn/problems/merge-k-sorted-lists/description/
    public ListNode mergeKLists1(ListNode[] lists) {
        //利用堆来解决问题,当然还可以用递归来解决
        PriorityQueue<ListNode> heap=new PriorityQueue<>((v1, v2)->v1.val-v2.val);
        //将所有头节点放到堆中
        for(ListNode head:lists){
            if(head!=null){
                heap.offer(head);
            }
        }
        //合并链表
        ListNode newHead=new ListNode(0);
        ListNode prev=newHead;
        while(!heap.isEmpty()){
            ListNode t=heap.poll();
            prev.next=t;
            prev=t;
            if(t.next!=null){
                heap.offer(t.next);
            }
        }
        return newHead.next;
    }
    //下面是递归来解决上面的问题
    public ListNode mergeKLists2(ListNode[] lists) {
        return merge(lists,0,lists.length-1);
    }
    public ListNode merge(ListNode[] lists,int left,int right){
        if(left>right){
            return null;
        }
        if(left==right){
            return lists[left];
        }
        int mid=(left+right)/2;
        ListNode l1=merge(lists,left,mid);
        ListNode l2=merge(lists,mid+1,right);
        //合并两个有序列表
        return mergeTwoList(l1,l2);
    }
    public ListNode mergeTwoList(ListNode l1,ListNode l2){
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode newHead=new ListNode(0);
        ListNode prev=newHead;
        ListNode cur1=l1;
        ListNode cur2=l2;
        while(cur1!=null&&cur2!=null){
            if(cur1.val<=cur2.val){
                prev.next=cur1;
                prev=cur1;
                cur1=cur1.next;
            }else{
                prev.next=cur2;
                prev=cur2;
                cur2=cur2.next;
            }
        }
        if(cur1!=null){
            prev.next=cur1;
        }
        if(cur2!=null){
            prev.next=cur2;
        }
        return newHead.next;
    }
}
